We study the problem of collective tree exploration in which a team of $k$ mobile agents must collectively visit all nodes of an unknown tree in as few moves as possible. The agents all start from the root and discover adjacent edges as they progress in the tree. Communication is distributed in the sense that agents share information by reading and writing on whiteboards located at all nodes. Movements are asynchronous, in the sense that the speeds of all agents are controlled by an adversary at all times. All previous competitive guarantees for collective tree exploration are either distributed but synchronous, or asynchronous but centralized. In contrast, we present a distributed asynchronous algorithm that explores any tree of $n$ nodes and depth $D$ in at most $2n+O(k^2 2^kD)$ moves, i.e., with a regret that is linear in $D$, and a variant algorithm with a guarantee in $O(k/\log k)(n+kD)$, i.e., with a competitive ratio in $O(k/\log k)$. We note that our regret guarantee is asymptotically optimal (i.e., $1$-competitive) from the perspective of average-case complexity. We then present a new general lower bound on the competitive ratio of asynchronous collective tree exploration, in $Ω(\log^2 k)$. This lower bound applies to both the distributed and centralized settings, and improves upon the previous lower bound in $Ω(\log k)$.

We study the problem of collective tree exploration (CTE) where a team of $k$ agents is tasked to traverse all the edges of an unknown tree as fast as possible, assuming complete communication between the agents. In this paper, we present an algorithm performing collective tree exploration in only $2n/k+O(kD)$ rounds, where $n$ is the number of nodes in the tree, and $D$ is the tree depth. This leads to a competitive ratio of $O(\sqrt{k})$ for collective tree exploration, the first polynomial improvement over the initial $O(k/\log(k))$ ratio of [FGKP06]. Our analysis relies on a game with robots at the leaves of a continuously growing tree, which is presented in a similar manner as the `evolving tree game' of [BCR22], though its analysis and applications differ significantly. This game extends the `tree-mining game' (TM) of [Cos23] and leads to guarantees for an asynchronous extension of collective tree exploration (ACTE). Another surprising consequence of our results is the existence of algorithms $\{A_k\}_{k\in \mathbb{N}}$ for layered tree traversal (LTT) with cost at most $2L/k+O(kD)$, where $L$ is the sum of edge lengths and $D$ is the tree depth. For the case of layered trees of width $w$ and unit edge lengths, our guarantee is thus in $O(\sqrt{w}D)$.

In collective tree exploration, a team of $k$ mobile agents is tasked to go through all edges of an unknown tree as fast as possible. An edge of the tree is revealed to the team when one agent becomes adjacent to that edge. The agents start from the root and all move synchronously along one adjacent edge in each round. Communication between the agents is unrestricted, and they are, therefore, centrally controlled by a single exploration algorithm. The algorithm's guarantee is typically compared to the number of rounds required by the agents to go through all edges if they had known the tree in advance. This quantity is at least $\max\{2n/k,2D\}$ where $n$ is the number of nodes and $D$ is the tree depth. Since the introduction of the problem by [FGKP04], two types of guarantees have emerged: the first takes the form $r(k)(n/k+D)$, where $r(k)$ is called the competitive ratio, and the other takes the form $2n/k+f(k,D)$, where $f(k,D)$ is called the competitive overhead. In this paper, we present the first algorithm with linear-in-$D$ competitive overhead, thereby reconciling both approaches. Specifically, our bound is in $2n/k + O(k^{\log_2(k)-1} D)$ and leads to a competitive ratio in $O(k/\exp(\sqrt{\ln 2\ln k}))$. This is the first improvement over $O(k/\ln k)$ since the introduction of the problem, twenty years ago. Our algorithm is developed for an asynchronous generalization of collective tree exploration (ACTE). It belongs to a broad class of locally-greedy exploration algorithms that we define. We show that the analysis of locally-greedy algorithms can be seen through the lens of a 2-player game that we call the tree-mining game and which could be of independent interest.